home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 25 / Cream of the Crop 25.iso / compress / tar321__.zip / SOURCES.ZIP / UNLZW.C < prev    next >
C/C++ Source or Header  |  1980-07-24  |  9KB  |  291 lines
  1. /* unlzw.h - this is part of the Tar program (see file define.h) */
  2.  
  3. #include <stdio.h>
  4. #include "modern.h"
  5. #include "compress.h"
  6. #include "lzwhead.h"
  7. #include "lzwbits.h"
  8.  
  9. #ifdef MSDOS
  10. #    include <stdlib.h>
  11. #else
  12.     char *malloc();
  13.     void free();
  14. #endif
  15.  
  16. static int d_n_bits;    /* number of bits/code */
  17. static int d_maxbits = BITS;    /* user settable max # bits/code */
  18. static code_int d_maxcode;    /* maximum code, given n_bits */
  19. /* should NEVER generate this code */
  20. static code_int d_maxmaxcode = (code_int)1 << BITS;
  21.  
  22. #ifdef XENIX_16
  23.   static unsigned short *decodet[MAXPAGES] = { NULL };
  24.   static char_type *stab[NUMPAGES];
  25.  
  26. # define tab_prefixof(i) (decodet[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  27. # define tab_suffixof(i) (stab[(int)((i) >> PAGEXP)][(int)(i) & PAGEMASK])
  28. #else
  29.   static unsigned short *decodet = NULL;
  30.   static char_type *stab;
  31.  
  32. # define tab_prefixof(i) decodet[i]
  33. # define tab_suffixof(i) stab[i]
  34. #endif
  35.  
  36. static char_type *de_stack = NULL; /* output stack */
  37. static code_int d_free_ent = 0;
  38.  
  39. /* block compression parameters -- after all codes are */
  40. /* used up, and compression rate changes, start over.  */
  41. static int d_block_compress = BLOCK_MASK;
  42. static int d_clear_flg = 0;
  43. static count_int d_checkpoint = CHECK_GAP;
  44.  
  45. /* interface function pointers */
  46. static int  (*getbyte) __ARGS__((void));
  47.  
  48. static int getpiece __ARGS__((char *, int));
  49.  
  50. static int getpiece(buf, nbytes)
  51. char buf[]; int nbytes;
  52. {
  53.    register i, b;
  54.  
  55.    for (i=0; i<nbytes && (b=(*getbyte)())!=EOF; i++) buf[i] = b;
  56.    return i;
  57. }
  58.  
  59. static code_int getcode __ARGS__((void))
  60. /* Read one code, returns -1 on EOF */
  61. {
  62. #ifndef vax
  63.    static char_type rmask[] = {0x00,0x01,0x03,0x07,0x0f,0x1f,0x3f,0x7f};
  64. #endif
  65. /* On the VAX, it is important to have the register declarations */
  66. /* in exactly the order given, or the asm will break. */
  67.    register code_int code;
  68.    static int offset = 0, size = 0;
  69.    static char_type buf[BITS];
  70.    register int r_off, bits;
  71.    register char_type *bp = buf;
  72.  
  73.    if (d_clear_flg > 0 || offset >= size || d_free_ent > d_maxcode ) {
  74.       /*
  75.        * If the next entry will be too big for the current code
  76.        * size, then we must increase the size.  This implies reading
  77.        * a new buffer full, too.
  78.        */
  79.       if (d_free_ent > d_maxcode) {
  80.          d_maxcode = ++d_n_bits == d_maxbits ?
  81.                         d_maxmaxcode : MAXCODE(d_n_bits);
  82.       }
  83.       if (d_clear_flg > 0) {
  84.          d_maxcode = MAXCODE(d_n_bits = INIT_BITS);
  85.          d_clear_flg = 0;
  86.       }
  87.       if ((size = getpiece((char *)buf, d_n_bits)) <= 0) return -1; /* EOF */
  88.       offset = 0;
  89.       /* Round size down to integral number of codes */
  90.       size = (size << 3) - (d_n_bits - 1);
  91.    }
  92.    r_off = offset;
  93.    bits = d_n_bits;
  94. #ifdef vax
  95.    asm( "extzv      r10,r9,(r8),r11" );
  96. #else
  97.    /* Get to the first byte. */
  98.    bp += (r_off >> 3);
  99.    r_off &= 7;
  100.    /* Get first part (low order bits) */
  101.    code = char_to_byte((unsigned)(*bp++)) >> r_off;
  102.    r_off = 8 - r_off;    /* now, offset into code word */
  103.    if ((bits -= r_off) >= 8) {
  104.       /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
  105.       code |= char_to_byte((unsigned)(*bp++)) << r_off;
  106.        r_off += 8;
  107.        bits -= 8;
  108.    }
  109.    /* high order bits. */
  110.    code |= (unsigned)(*bp & rmask[bits]) << r_off;
  111. #endif
  112.    offset += d_n_bits;
  113.    return code;
  114. }
  115.  
  116. int z_getmem(wishbits)
  117. int wishbits;
  118. {
  119. #ifdef XENIX_16
  120.    register i, j; code_int l;
  121. #endif
  122.    code_int dhsize = _HSIZE;
  123.  
  124.    if (de_stack) return d_maxbits;
  125.    if (wishbits > BITS) wishbits = BITS;
  126.    d_maxbits = wishbits;
  127.    d_maxmaxcode = (code_int)1 << d_maxbits;
  128.  
  129.    de_stack = (char_type *)malloc(sizeof(char_type) * 8000);
  130.    if (!de_stack) return -1;
  131.    if      (wishbits >= 16) dhsize = 69001L;
  132.    else if (wishbits >= 15) dhsize = 35023L;
  133.    else if (wishbits >= 14) dhsize = 18013L;
  134.    else if (wishbits >= 13) dhsize = 9001L;
  135.    else                     dhsize = 5003L;
  136. #ifdef XENIX_16
  137.    for (l=(code_int)1<<wishbits, i=0; i<NUMPAGES && l>0; i++) {
  138.       j = l<PAGESIZE ? (int)l : PAGESIZE;
  139.       stab[i] = (char_type *)malloc(sizeof(char_type) * j);
  140.       if (!stab[i]) return -1;
  141.       l -= j;
  142.    }
  143.    for (l=dhsize, i=0; i<MAXPAGES && l>0; i++) {
  144.       j = l > PAGESIZE ? PAGESIZE : (int)l;
  145.       decodet[i] = (unsigned short *)malloc(sizeof(unsigned short)*j);
  146.       if (!decodet[i]) break;
  147.       l -= j;
  148.    }
  149.    l = dhsize - l;
  150.    if      (l >= 69001L) { j = 16; dhsize = 69001L; }
  151.    else if (l >= 35023L) { j = 15; dhsize = 35023L; }
  152.    else if (l >= 18013)  { j = 14; dhsize = 18012L; }
  153.    else if (l >= 9001)   { j = 13; dhsize =  9001L; }
  154.    else if (l >= 5003)   { j = 12; dhsize =  5003L; }
  155.    else return -1;
  156.    if (d_maxbits > j) d_maxbits = j;
  157. #else
  158.    if ((decodet=(unsigned short*)malloc(sizeof(*decodet)*dhsize))==NULL ||
  159.        (stab   =(char_type *)malloc(sizeof(*stab) * (1<<wishbits))) == NULL)
  160.       return -1;
  161. #endif
  162.    return d_maxbits;
  163. }
  164.  
  165. void z_relmem()
  166. {
  167. #ifdef XENIX_16
  168.    register i;
  169. #endif
  170.  
  171.    if (de_stack != NULL) {
  172.       free((char*)de_stack); de_stack = NULL;
  173. #ifdef XENIX_16
  174.       for (i=0; i<NUMPAGES && stab[i]!=NULL; i++) free((char*)(stab[i]));
  175.       if (i >= NUMPAGES) {
  176.          for (i=0; i<MAXPAGES && decodet[i]!=NULL; i++)
  177.             free((char*)(decodet[i]));
  178.       }
  179. #else
  180.       if (decodet != NULL) {
  181.          free((char*)decodet);
  182.          if (stab != NULL) free((char*)stab);
  183.       }
  184. #endif
  185.    }
  186. }
  187.  
  188. /* This routine adapts to the codes in the file building the "string" table */
  189. /* on-the-fly; requiring no table to be stored in the compressed file.      */
  190.  
  191. static notfirst = 0;
  192. static char_type *stackp;
  193. static code_int oldcode;
  194. static int finchar;
  195. static mbits;
  196.  
  197. int dbegin(getb)
  198. int (*getb)();
  199. {
  200.    register k;
  201.  
  202.    getbyte = getb;
  203.    d_clear_flg = 0;
  204.    d_checkpoint = CHECK_GAP;
  205.  
  206.    if ((*getbyte)() != LZW_0TH_MAGIC || (*getbyte)() != LZW_1ST_MAGIC)
  207.       return 1;
  208.  
  209.    d_maxbits = (*getbyte)(); /* set -b from file */
  210.    d_block_compress = d_maxbits & BLOCK_MASK;
  211.    d_maxbits &= BIT_MASK;
  212.    if ((mbits = z_getmem(d_maxbits)) < 0) return -1;
  213.    if (d_maxbits > mbits) {
  214.       k = -d_maxbits; d_maxbits = mbits; return k;
  215.    }
  216.    d_maxmaxcode = (code_int)1 << d_maxbits;
  217.    /* As above, initialize the first 256 entries in the table. */
  218.    d_maxcode = MAXCODE(d_n_bits = INIT_BITS);
  219.    for (k = 255; k >= 0; k--) {
  220.       tab_prefixof(k) = 0;
  221.       tab_suffixof(k) = (char_type)k;
  222.    }
  223.    d_free_ent = d_block_compress ? FIRST : 256;
  224.    stackp = de_stack;
  225.    finchar = (int)(oldcode = getcode());
  226.    notfirst = 0;
  227.    return 0;
  228. }
  229.  
  230. int dpiece(buf, len)
  231. char buf[];
  232. int len;
  233. {
  234.    static code_int code, incode;
  235.    register k = 0;
  236.  
  237.    if (!notfirst) {
  238.       notfirst = 1;
  239.       /* EOF already? Get out of here */
  240.       if (oldcode == -1) goto endfile;
  241.       /* first code must be 8 bits = char */
  242.       ++k; *buf++ = (char)finchar;
  243.    }
  244.    for (;;) {
  245.       if (stackp == de_stack) {
  246.          if ((code = getcode()) < 0) break;
  247.          if (code == CLEAR && d_block_compress) {
  248.             for (code=255; code >= 0; code--) tab_prefixof(code) = 0;
  249.             d_clear_flg = 1;
  250.             d_free_ent = FIRST - 1;
  251.             if ((code = getcode()) == -1) break; /* O, untimely death! */
  252.          }
  253.          incode = code;
  254.          /* Special case for KwKwK string. */
  255.          if (code >= d_free_ent) {
  256.             *stackp++ = finchar;
  257.             code = oldcode;
  258.          }
  259.          /* Generate output characters in reverse order */
  260. #ifdef SIGNED_COMPARE_SLOW
  261.          while ((unsigned long)code >= (unsigned long)256)
  262. #else
  263.          while (code >= 256)
  264. #endif
  265.          {
  266.             *stackp++ = tab_suffixof(code);
  267.             code = tab_prefixof(code);
  268.          }
  269.          *stackp++ = finchar = tab_suffixof(code);
  270.       }
  271.       /* And put them out in forward order */
  272.       do {
  273.          if (k >= len) goto end;
  274.          ++k; *buf++ = *--stackp;
  275.       } while (stackp > de_stack);
  276.  
  277.       /* Generate the new entry. */
  278.       if ((code=d_free_ent) < d_maxmaxcode) {
  279.          tab_prefixof(code) = (unsigned short)oldcode;
  280.          tab_suffixof(code) = finchar;
  281.          d_free_ent = code+1;
  282.       }
  283.       /* Remember previous code. */
  284.       oldcode = incode;
  285.    }
  286. endfile:
  287.    d_maxbits = mbits; /* We shall need in it at the next file */
  288. end:
  289.    return k;
  290. }
  291.